{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Replace Non-Coprime Numbers in Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: replaceNonCoprimes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #替换数组中的非互质数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 。请你对数组执行下述操作：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>从 <code>nums</code> 中找出 <strong>任意</strong> 两个 <strong>相邻</strong> 的 <strong>非互质</strong> 数。</li>\n",
    "\t<li>如果不存在这样的数，<strong>终止</strong> 这一过程。</li>\n",
    "\t<li>否则，删除这两个数，并 <strong>替换</strong> 为它们的 <strong>最小公倍数</strong>（Least Common Multiple，LCM）。</li>\n",
    "\t<li>只要还能找出两个相邻的非互质数就继续 <strong>重复</strong> 这一过程。</li>\n",
    "</ol>\n",
    "\n",
    "<p>返回修改后得到的 <strong>最终</strong> 数组。可以证明的是，以 <strong>任意</strong> 顺序替换相邻的非互质数都可以得到相同的结果。</p>\n",
    "\n",
    "<p>生成的测试用例可以保证最终数组中的值 <strong>小于或者等于</strong> <code>10<sup>8</sup></code> 。</p>\n",
    "\n",
    "<p>两个数字 <code>x</code> 和 <code>y</code> 满足 <strong>非互质数</strong> 的条件是：<code>GCD(x, y) &gt; 1</code> ，其中 <code>GCD(x, y)</code> 是 <code>x</code> 和 <code>y</code> 的 <strong>最大公约数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [6,4,3,2,7,6,2]\n",
    "<strong>输出：</strong>[12,7,6]\n",
    "<strong>解释：</strong>\n",
    "- (6, 4) 是一组非互质数，且 LCM(6, 4) = 12 。得到 nums = [<em><strong>12</strong></em>,3,2,7,6,2] 。\n",
    "- (12, 3) 是一组非互质数，且 LCM(12, 3) = 12 。得到 nums = [<em><strong>12</strong></em>,2,7,6,2] 。\n",
    "- (12, 2) 是一组非互质数，且 LCM(12, 2) = 12 。得到 nums = [<em><strong>12</strong></em>,7,6,2] 。\n",
    "- (6, 2) 是一组非互质数，且 LCM(6, 2) = 6 。得到 nums = [12,7,<em><strong>6</strong></em>] 。\n",
    "现在，nums 中不存在相邻的非互质数。\n",
    "因此，修改后得到的最终数组是 [12,7,6] 。\n",
    "注意，存在其他方法可以获得相同的最终数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,2,1,1,3,3,3]\n",
    "<strong>输出：</strong>[2,1,1,3]\n",
    "<strong>解释：</strong>\n",
    "- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,<em><strong>3</strong></em>,3] 。\n",
    "- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,<em><strong>3</strong></em>] 。\n",
    "- (2, 2) 是一组非互质数，且 LCM(2, 2) = 2 。得到 nums = [<em><strong>2</strong></em>,1,1,3] 。\n",
    "现在，nums 中不存在相邻的非互质数。 \n",
    "因此，修改后得到的最终数组是 [2,1,1,3] 。 \n",
    "注意，存在其他方法可以获得相同的最终数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>生成的测试用例可以保证最终数组中的值 <strong>小于或者等于</strong> <code>10<sup>8</sup></code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [replace-non-coprime-numbers-in-array](https://leetcode.cn/problems/replace-non-coprime-numbers-in-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [replace-non-coprime-numbers-in-array](https://leetcode.cn/problems/replace-non-coprime-numbers-in-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,4,3,2,7,6,2]', '[2,2,1,1,3,3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        def gcd(x,y):\n",
    "            if x<y:\n",
    "                x,y=y,x\n",
    "            #x大一些\n",
    "            r=x%y\n",
    "            while r:\n",
    "                x=y\n",
    "                y=r\n",
    "                r=x%y\n",
    "            return y\n",
    "        stack=[nums[0]]\n",
    "        #这里要while，一直pop到这两个互质为止，否则你下一村循环又从右边的数开始看了(栈内就是很多内层的while，保证一直压进去的)\n",
    "        #因为要一直pop到互质为止，也就是你压进去一个数，然后就会进行一个退栈的操作，所以可以先把这个数压进去，然后再看栈顶两个数情况\n",
    "        for num in nums[1:]:\n",
    "            while stack and gcd(stack[-1],num)!=1:\n",
    "                num=num*stack[-1]//gcd(stack[-1],num)\n",
    "                stack.pop()\n",
    "            stack.append(num)\n",
    "        return stack\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        stk = [nums[0]]\n",
    "        for x in nums[1:]:\n",
    "            while stk and gcd(stk[-1], x) != 1:\n",
    "                x = stk[-1] * x // gcd(stk[-1], x)\n",
    "                stk.pop()\n",
    "            stk.append(x)\n",
    "        return stk\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        def gcd(x,y):\n",
    "            if x<y:\n",
    "                x,y=y,x\n",
    "            #x大一些\n",
    "            r=x%y\n",
    "            while r:\n",
    "                x=y\n",
    "                y=r\n",
    "                r=x%y\n",
    "            return y\n",
    "        stack=[nums[0]]\n",
    "        #这里要while，一直pop到这两个互质为止，否则你下一村循环又从右边的数开始看了(栈内就是很多内层的while，保证一直压进去的)\n",
    "        #因为要一直pop到互质为止，也就是你压进去一个数，然后就会进行一个退栈的操作，所以可以先把这个数压进去，然后再看栈顶两个数情况\n",
    "        for num in nums[1:]:\n",
    "            g=gcd(stack[-1],num)\n",
    "            while stack and g!=1:\n",
    "                num=num*stack[-1]//g\n",
    "                stack.pop()\n",
    "                if not stack:\n",
    "                    break\n",
    "                g=gcd(stack[-1],num)\n",
    "            stack.append(num)\n",
    "        return stack\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        stack = [nums[0]]\n",
    "        def gcd(a, b):\n",
    "            if b == 0:\n",
    "                return a\n",
    "            if a < b:\n",
    "                a, b = b, a\n",
    "            return gcd(b, a % b)\n",
    "        for x in nums[1:]:\n",
    "            while stack:\n",
    "                top = stack.pop()\n",
    "                g = gcd(top, x)\n",
    "                if g == 1:\n",
    "                    stack.append(top)\n",
    "                    break\n",
    "                x = x * top // g\n",
    "            stack.append(x)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        for c in nums:\n",
    "            st.append(c)\n",
    "            while len(st) > 1:\n",
    "                x,y = st[-1],st[-2]\n",
    "                g = gcd(x,y)\n",
    "                if g == 1:break\n",
    "                st.pop()\n",
    "                st[-1] *= x//g\n",
    "        return st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        def back():\n",
    "            while len(ans) > 1:\n",
    "                gg = math.gcd(ans[-1], ans[-2])\n",
    "                if gg == 1:\n",
    "                    break\n",
    "                else:\n",
    "                    ans[-2] = (ans[-2] * ans[-1]) // gg\n",
    "                    ans.pop()\n",
    "        ans = []\n",
    "        for n in nums:\n",
    "            if not ans:\n",
    "                ans.append(n)\n",
    "                continue\n",
    "            g = math.gcd(ans[-1], n)\n",
    "            if g == 1:\n",
    "                back()\n",
    "            gg = math.gcd(ans[-1], n)\n",
    "            if gg == 1:\n",
    "                ans.append(n)\n",
    "            else:\n",
    "                ans[-1] = (ans[-1] * n) // g\n",
    "                back()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        def gcd(x, y):\n",
    "            if y == 0:\n",
    "                return x\n",
    "            return gcd(y, x % y)\n",
    "        stk = [nums[0]]\n",
    "        for x in nums[1:]:\n",
    "            while stk and gcd(stk[-1], x) != 1:\n",
    "                lcm = stk[-1] * x // gcd(stk[-1], x)\n",
    "                stk.pop()\n",
    "                x = lcm\n",
    "            stk.append(x)\n",
    "        return stk\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        s = []\n",
    "        for num in nums:\n",
    "            s.append(num)\n",
    "            while len(s) > 1:\n",
    "                x, y = s[-1], s[-2]\n",
    "                g = gcd(x, y)\n",
    "                if g == 1: break\n",
    "                s.pop()\n",
    "                s[-1] *= x // g\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        stk = []\n",
    "        for num in nums:\n",
    "            stk.append(num)\n",
    "            while len(stk) >= 2:\n",
    "                x,y = stk[-1],stk[-2]\n",
    "                g = gcd(x,y)\n",
    "                if g == 1:\n",
    "                    break\n",
    "                stk.pop()\n",
    "                stk[-1] = lcm(x,y)\n",
    "        return stk\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        def back():\n",
    "            while len(ans) > 1:\n",
    "                gg = math.gcd(ans[-1], ans[-2])\n",
    "                if gg == 1:\n",
    "                    break\n",
    "                else:\n",
    "                    ans[-2] = (ans[-2] * ans[-1]) // gg\n",
    "                    ans.pop()\n",
    "        ans = []\n",
    "        for n in nums:\n",
    "            ans.append(n)\n",
    "            back()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, A: List[int]) -> List[int]:\n",
    "        stk = []\n",
    "        for x in A:\n",
    "            stk.append(x)\n",
    "            while len(stk) > 1:\n",
    "                x, y = stk[-1], stk[-2]\n",
    "                g = gcd(x, y)\n",
    "                if g == 1: break\n",
    "                stk.pop()\n",
    "                stk[-1] *= x // g\n",
    "        return stk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        s = []\n",
    "        for x in nums:\n",
    "            s.append(x)\n",
    "            while len(s) > 1:\n",
    "                x, y = s[-1], s[-2]\n",
    "                if gcd(x, y) == 1:\n",
    "                    break\n",
    "                s.pop()\n",
    "                s[-1] = x * y // gcd(x,y)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\r\n",
    "        s = []\r\n",
    "        for num in nums:\r\n",
    "            s.append(num)\r\n",
    "            while len(s) > 1:\r\n",
    "                x, y = s[-1], s[-2]\r\n",
    "                g = gcd(x, y)\r\n",
    "                if g == 1: break\r\n",
    "                s.pop()\r\n",
    "                s[-1] *= x // g\r\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for x in nums:\n",
    "            stack.append(x)\n",
    "            while len(stack) > 1:\n",
    "                x, y = stack[-1], stack[-2]\n",
    "                g = gcd(x, y)\n",
    "                if g == 1: break\n",
    "                stack.pop()\n",
    "                stack[-1] *= x // g\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        a = []\n",
    "        for i in nums:\n",
    "            while a and gcd(i, a[-1]) != 1:\n",
    "                i = lcm(i, a[-1])\n",
    "                a.pop()\n",
    "            a.append(i)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for e in nums:\n",
    "            while stack and gcd(stack[-1], e) != 1:\n",
    "                ee = stack.pop()\n",
    "                e = lcm(ee, e)\n",
    "            stack.append(e)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        stk = []\n",
    "        for n in nums:\n",
    "            val = n\n",
    "            while len(stk):\n",
    "                g = gcd(stk[-1], val)\n",
    "                if g == 1:\n",
    "                    break\n",
    "                val = val*stk.pop()//g\n",
    "            stk.append(val)\n",
    "        return stk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for n in nums:\n",
    "            while stack:\n",
    "                g = gcd(n, stack[-1])\n",
    "                if g == 1: break\n",
    "                n *= stack.pop() // g\n",
    "            stack.append(n)\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        s=[]\n",
    "        for x in nums:\n",
    "            while s and gcd(x,s[-1])>1:\n",
    "                y=s.pop()\n",
    "                x=lcm(x,y)\n",
    "            s.append(x)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for num in nums:\n",
    "            cur = num\n",
    "            while stack and gcd(stack[-1], cur) > 1:\n",
    "                t = stack.pop()\n",
    "                cur = lcm(t, cur)\n",
    "            \n",
    "            stack.append(cur)\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for num in nums:\n",
    "            stack.append(num)\n",
    "            while len(stack) >= 2 and math.gcd(stack[-1], stack[-2]) > 1:\n",
    "                a, b = stack.pop(), stack.pop()\n",
    "                stack.append(math.lcm(a, b))\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        for num in nums:\n",
    "            while st and gcd(st[-1], num) > 1:\n",
    "                num = lcm(st.pop(), num)\n",
    "            st.append(num)\n",
    "\n",
    "        return st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        def gcd(x, y):\n",
    "            while y:\n",
    "                tmp = y\n",
    "                y = x % y \n",
    "                x = tmp \n",
    "            return x \n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            stack.append(nums[i])\n",
    "            while len(stack) > 1 and gcd(stack[-1], stack[-2]) != 1:\n",
    "                last = stack.pop()\n",
    "                stack[-1] = last * stack[-1] // gcd(last, stack[-1])\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            temp = nums[i]\n",
    "            while st and gcd(temp,st[-1]) != 1:\n",
    "                temp = lcm(temp,st.pop())\n",
    "            st.append(temp)\n",
    "        return st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for x in nums:\n",
    "            while ans and gcd(ans[-1], x) > 1:\n",
    "                x = lcm(x, ans[-1])\n",
    "                ans.pop()\n",
    "            ans.append(x)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        for num in nums:\n",
    "            while stack:\n",
    "                t = stack[-1]\n",
    "                m = math.gcd(t, num)\n",
    "                if m > 1:\n",
    "                    stack.pop(-1)\n",
    "                    num = num * t // m\n",
    "                else:\n",
    "                    break\n",
    "            stack.append(num)\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def gcd(self, a, b):\n",
    "        # while b!=0:\n",
    "        #     a, b = b, a%b\n",
    "        return math.gcd(a, b)\n",
    "\n",
    "    def lcm(self, a, b):\n",
    "        return abs(a*b)//self.gcd(a,b)\n",
    "\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        self.nums = nums\n",
    "\n",
    "        # if len(self.nums) == 1:\n",
    "        #     return nums\n",
    "        # else:\n",
    "        #     left = 0\n",
    "        #     right = 1\n",
    "\n",
    "        # while right<len(self.nums) and len(self.nums)>1:\n",
    "        #     # print(left, right, len(self.nums))\n",
    "        #     # print(self.nums)\n",
    "        #     g = self.gcd(self.nums[left], self.nums[right])\n",
    "        #     if g != 1:\n",
    "        #         a = self.nums.pop(left)\n",
    "        #         b = self.nums.pop(left)\n",
    "        #         # print(left, right, self.nums)\n",
    "        #         self.nums.insert(left, abs(a*b)//g )\n",
    "        #         # print(self.nums)\n",
    "        #         g = self.gcd(self.nums[left-1], self.nums[left])\n",
    "        #         while left != 0 and g != 1:\n",
    "        #             a = self.nums.pop(left-1)\n",
    "        #             b = self.nums.pop(left-1)\n",
    "        #             self.nums.insert(left-1, abs(a*b)//g )\n",
    "        #             # print(self.nums)\n",
    "        #             left = left-1\n",
    "        #         right = left + 1\n",
    "        #     else:\n",
    "        #         left += 1\n",
    "        #         right = left+1\n",
    "\n",
    "        # return self.nums\n",
    "\n",
    "        self.result = [self.nums.pop(0)]\n",
    "\n",
    "        for n in self.nums:\n",
    "            while self.result:\n",
    "                g = math.gcd(self.result[-1], n)\n",
    "                if g > 1:\n",
    "                    n = self.result[-1] // g*n\n",
    "                    self.result.pop()\n",
    "                else:\n",
    "                    break\n",
    "            self.result.append(n)\n",
    "            \n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:\n",
    "        def replace(a):\n",
    "            ans = []\n",
    "            n = len(a)\n",
    "            cur = a[0]\n",
    "            for i in range(1, n):\n",
    "                x = a[i]\n",
    "                # print(f'{cur,x, gcd(cur,x)}')\n",
    "                if gcd(cur, x) == 1:\n",
    "                    ans.append(cur)\n",
    "                    cur = x\n",
    "                else:\n",
    "                    cur = cur * x // gcd(cur, x)\n",
    "            ans.append(cur)\n",
    "            return ans\n",
    "        \n",
    "        while True:\n",
    "            ans = replace(nums)\n",
    "            ans2 = replace(nums[::-1])\n",
    "            \n",
    "            if len(ans) == len(nums):\n",
    "                return ans\n",
    "            elif len(ans) < len(ans2):\n",
    "                nums = ans\n",
    "            else:\n",
    "                nums = ans2[::-1]\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
